#include <string>
#include <vector>

using namespace std;

// 不同的子序列 II
// 给定一个字符串 s，计算 s 的 不同非空子序列 的个数
// 因为结果可能很大，所以返回答案需要对 10^9 + 7 取余
// 字符串的 子序列 是经由原字符串删除一些（也可能不删除）
// 字符但不改变剩余字符相对位置的一个新字符串
// 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是
// 测试链接 : https://leetcode.cn/problems/distinct-subsequences-ii/

class Solution 
{
public:
    // 时间复杂度 O(n)，n 是字符串 s 的长度
    int distinctSubseqII(string s) 
    {
        const int MOD = 1e9 + 7;
        // cnt[i] : 以 'a' + i 字符结尾的不同子序列有多少个
        vector<int> cnt(26);
        int all = 1, newAdd;
        for(char ch : s)
        {
            // 纯新增（去重） ： all - 当前字符上一次记录
            newAdd = (all - cnt[ch - 'a'] + MOD) % MOD;
            // 当前字符记录 += 纯新增
            cnt[ch - 'a'] = (cnt[ch - 'a'] + newAdd) % MOD;
            // all += 纯新增
            all = (all + newAdd) % MOD;
        }      
        // -1 去掉空集
        return (all - 1 + MOD) % MOD;
    }
};


class Solution 
{
public:
    const int MOD = 1e9 + 7;

    int distinctSubseqII1(string s) 
    {
        int n = s.size();
        // f[i][j] : 前 i 个字符组成以 j 结尾的不同非空子序列的个数
        vector<array<int, 26>> f(n);
        f[0][s[0] - 'a'] = 1;
        for(int i = 1; i < n; ++i)
        {
            // 不以 s[i] 结尾
            f[i] = f[i - 1]; 
            // 以 s[i] 结尾
            f[i][s[i] - 'a'] = accumulate(f[i - 1].begin(), f[i - 1].end(), 1L) % MOD;
        }
        return accumulate(f[n - 1].begin(), f[n - 1].end(), 0L) % MOD;
    }

    int distinctSubseqII2(string s) 
    {
        int f[26]{};
        for(char ch : s)
        {
            f[ch - 'a'] = accumulate(f, f + 26, 1L) % MOD;
        }
        return accumulate(f, f + 26, 0L) % MOD;
    }

    int distinctSubseqII3(string s) 
    {
        int f[26]{}, total = 0;
        for(char ch : s)
        {
            ch -= 'a';
            int other = total - f[ch]; // total 中不含 f[ch] 的部分（由于取模的原因，这里的减法可能会产生负数）
            f[ch] = 1 + total; // 更新 f[ch]
            total = ((f[ch] + other) % MOD + MOD) % MOD; // 更新 total，并保证 total 非负
        }
        return total;
    }
};